package practice;

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Day21 {
    //宽度优先遍历练习：
    //二叉树最大宽度：父子树如果编号为x，则左子树编号为2*x，右子树编号为2*x+1
    private int findMax(List<Integer> list) {
        int size = list.size();
        int left = 0;
        int right = size - 1;
        return list.get(right) - list.get(left) + 1;
    }
    public int widthOfBinaryTree(TreeNode root) {
        if(root == null) {
            return 0;
        }
        Queue<Object[]> queue = new LinkedList<>();
        queue.offer(new Object[]{root,1});
        int max = 1;
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            System.out.println("size:" + size);
            while(size-- != 0) {
                Object[] top = queue.poll();
                TreeNode topNode = (TreeNode)top[0];
                if(topNode.left != null) {
                    queue.offer(new Object[]{topNode.left,(Integer)top[1] * 2});
                }
                if(topNode.right != null) {
                    queue.offer(new Object[]{topNode.right,(Integer)top[1] * 2 + 1});
                }
                list.add((Integer)top[1]);
            }
            int ret = findMax(list);
            max = Math.max(max,ret);
        }
        return max;
    }
    //主持人调度（优先级队列）
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        Arrays.sort(startEnd, (a, b) -> {
            return a[0] <= b[0] ? -1 : 1;
            //return a[0] - b[0]; //可能超出范围，从小到大：a<b,返回-1;a=b,返回0;a>b，返回1;如果在不超出范围的前提下可以使用a-b，否则只能写成上面写法
        });
        PriorityQueue<Integer> heap = new PriorityQueue<>(); // ⼩根堆
        heap.offer(startEnd[0][1]);
        for (int i = 1; i < n; i++) {
            if (startEnd[i][0] >= heap.peek()) { // ⽆重叠
                heap.poll();
            }
            heap.offer(startEnd[i][1]);
        }
        return heap.size();
    }
}
